/*
 * addOne.cpp
 *
 *  Created on: Sep 4, 2012
 *      Author: jh238d
 */

#include <iostream>
#include <vector>
using namespace std;

vector<int> addOne(vector<int> arr){
	if(arr.size()==0){
		arr.push_back(1);
		return arr;
	}
	int carry = 0;
	arr[arr.size()-1]+=1;
	if(arr[arr.size()-1]==0)
		carry=1;
	int i = arr.size()-2;
	while(carry==1&&i>=0)
	{
		arr[i]+=carry;
		if(arr[i]==0)
			carry=1;
		else
			carry=0;
	}
	if(carry==1){
		arr.push_back(arr[arr.size()-1]);
		for(int i=arr.size()-2; i>=1;i--)
			arr[i]=arr[i-1];
		arr[0] = 1;
	}

	return arr;
}


